package offer;

public class buildTree_07 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
        return build(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);

    }

    public TreeNode build(int[] preorder, int preStart,int preEnd,
                      int[] inorder, int inStart,int inEnd){

        if(preStart > preEnd){
            return null;
        }

        int root = preorder[preStart];
        int inRootIndex=-1;
        for (int i = inStart; i <= inEnd; i++) {
            if(inorder[i] == root){
                inRootIndex = i;
                break;
            }
        }
        int leftLength = inRootIndex - inStart;

        TreeNode treeNode = new TreeNode(root);
        treeNode.left = build(preorder,preStart + 1,preStart + leftLength,
                inorder,inStart,inRootIndex - 1);
        treeNode.right = build(preorder,preStart + leftLength + 1,preEnd,
                inorder,inRootIndex + 1,inEnd);
        return treeNode;
    }
}
